#include <cstdio>

__int64 pow( __int64 a, __int64 b, __int64 c )
{
    if ( b == 0 )
        return 1;
    if ( b & 1 )
    {
        __int64 t = pow( a, b / 2, c );
        return ( t * t * a ) % c;
    }
    else
    {
        __int64 t = pow( a, b / 2, c );
        return ( t * t ) % c;
    }
}

int main( )
{
    __int64 a, b, c;
    int t;
    scanf("%d", &t);
    while ( t-- )
    {
        scanf("%I64d%I64d%I64d", &a, &b, &c);
        printf("%I64d\n", pow( a, b, c ));
    }
    return 0;
}
